{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.display import display, HTML\n",
    "display(HTML(\"<style>.container { width:100% !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 6- kNN, Normalization, Distance Metrics, Weighted Neighbours *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Table of Contents\n",
    "* [Lecture 6- kNN, Normalization, Distance Metrics, Weighted Neighbours *](#Lecture-6--kNN,-Normalization,-Distance-Metrics,-Weighted-Neighbours-*)\n",
    "\t* &nbsp;\n",
    "\t\t* [Content](#Content)\n",
    "\t\t* [Learning Outcomes](#Learning-Outcomes)\n",
    "* [Machine Learning using kNN](#Machine-Learning-using-kNN)\n",
    "\t* &nbsp;\n",
    "\t\t* [Measures of resemblance - (Euclidean)](#Measures-of-resemblance---%28Euclidean%29)\n",
    "\t* [kNN and the problem of scale](#kNN-and-the-problem-of-scale)\n",
    "\t* [kNN and data normalization/standardization](#kNN-and-data-normalization/standardization)\n",
    "\t\t* [Normalization (or Min-Max scaling)](#Normalization-%28or-Min-Max-scaling%29)\n",
    "\t\t* [Standardization (or Z-score normalization)](#Standardization-%28or-Z-score-normalization%29)\n",
    "\t* [Alternative similarity metrics](#Alternative-similarity-metrics)\n",
    "\t\t* [Cosine similarity](#Cosine-similarity)\n",
    "\t\t* [Jaccard similarity](#Jaccard-similarity)\n",
    "\t* [kNN and weighted decision aggregation](#kNN-and-weighted-decision-aggregation)\n",
    "\t\t* [Weighted average calculation](#Weighted-average-calculation)\n",
    "\t* [Introduction to Python's Machine Learning Toolkit Scikit-Learn](#Introduction-to-Python's-Machine-Learning-Toolkit-Scikit-Learn)\n",
    "\t\t* [Nearest Neighbor Search Algorithms (from http://scikit-learn.org)](#Nearest-Neighbor-Search-Algorithms-%28from-http://scikit-learn.org%29)\n",
    "\t\t* [Example (Regression)](#Example-%28Regression%29)\n",
    "\t\t* [Example (Classification)](#Example-%28Classification%29)\n",
    "\t* [When to Use k-Nearest Neighbours](#When-to-Use-k-Nearest-Neighbours)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. kNN and the problem of scale\n",
    "2. kNN and data normalization/standardization\n",
    "3. Euclidean, Cosine, Jaccard similarity distance metric\n",
    "4. kNN and weighted decision aggregation\n",
    "5. Intro to scikit-learn\n",
    "\n",
    "\n",
    "\\* Material in this notebook has been in part adapted from Sebastian Raschka, where the material can be found at\n",
    "http://nbviewer.ipython.org/github/rasbt/pattern_classification/blob/master/preprocessing/about_standardization_normalization.ipynb, http://scikit-learn.org"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Learning Outcomes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At the end of this lecture, you should be able to:\n",
    "\n",
    "* articulate the problem kNN faces on data with different scales\n",
    "* rescale data using normalization, standard score and absolute standard score\n",
    "* apply the Euclidean, Cosine and Jaccard Similarity metrics \n",
    "* apply weighted aggregation to the kNN algorithm\n",
    "* use the scikit-learn toolkit at an introductory level\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib as mpl\n",
    "import numpy as np\n",
    "import math \n",
    "from IPython.display import HTML, IFrame\n",
    "from sklearn import neighbors\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine Learning using kNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We saw how we could use linear regression to build a model that encodes a pattern in data. This model (equation), could then be used to either describe the relationship that exists in the data, or it could also be used as a way of predicting the response variable based on input variables.\n",
    "\n",
    "Here we will consider a machine learning (ML) algorithm that is arguably one of the most intuitive\n",
    "of all the machine learning algorithms. It is a **simple algorithm** but despite its simplicity, it is a **widely used algorithm in business and industrial settings**. \n",
    "\n",
    "The algorithm we will use is called **k-nearest neighbors (kNN)**. kNN is a curious ML algorithm as it **does not require us to explicitly build a model**. The data itself is the model. kNN is referred to as an instance-based learning algorithm, or a lazy learning algorithm as it does no computation until a classification is required. It is useful as it can be used in both regression (continuous value prediction) or classification (class label prediction) problems.\n",
    "\n",
    "So how does it work? As it turns out, it works very much like we do when faced with solving a problem. If you were asked to find out what the price for a 2 bedroom, 1 garage rental home in Albany would cost, how would you do it? You would most likely go to TradeMe as we did before or some other Real Estate agency website and look up a number of homes that are most similar to the requirement of \"2 bedroom, 1 garage\" home in Albany. Once you have these figures, you would then average and aggregate their prices to come up with your estimate. kNN works the same, where `k` represents the total number of instances closest to the data point you are wanting to classify."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "display(IFrame(src = \"https://helloacm.com/wp-content/uploads/2016/03/2012-10-26-knn-concept.png\", width=1000, height=700))\n",
    "# image source: https://helloacm.com/a-short-introduction-to-k-nearest-neighbors-algorithm/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Measures of resemblance - (Euclidean)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This brings us to the next point. **How do we determine how close something is to something else? To what degree does one item resemble another?**\n",
    "\n",
    "**resemblance quantifies the extent to which two things are similar or different to one another.**\n",
    "\n",
    "There are many resemblance metrics we can use, in this example we will consider the Euclidean distance. The resemblance metric in kNN forms the other part of the model. We calculate $d$ as the distance between points $x$ and $y$, having 2 features as follows:\n",
    "\n",
    "\n",
    "$ d(x, y) = \\sqrt{ (x_i-y_i)^2 + (x_j-y_j)^2}.$\n",
    "\n",
    "The above distance measure works well for a house query where we want to know how close house $x$ is to house $y$ given that both $x$ and $y$ have 2 features, $i$ and $j$ to represent a feature for `bedroom` and a feature for `garage`. But what if you wanted to find out how similar 2 houses were based on more than two features such as houses with \"2 bedrooms, 2 bathrooms, 1 garage, 2 living areas, 150m$^2$\"? Euclidean distance can easily be generalized to multiple features as follows: \n",
    "\n",
    "$d(x, y) = \\sqrt{(x_1- y_1)^2 + (x_2 - y_2)^2+...+(x_i - y_i)^2+...+(x_n - y_n)^2}.$\n",
    "\n",
    "In order to find the `k` most similar data points to $x$, we therefore must calculate the **similarity** ($d$ values) of $x$ to all the $y$s in the dataset. Then we must **order** the list of $d$ values from smallest to greatest, and **select the `k` first values** in the list. All that remains to be done then is to take the house price of the `k` values and find the mean. The mean value then represents our prediction for the house price given the requirements.\n",
    "\n",
    "The tricky part is selecting the **size of `k`**. If the dataset were perfect, then `k=1` would be enough to return the correct answer. However, this is almost never the case and so we need to aggregate data from several neghbours in order to account for `noise` that might exist in the data. **Having a `k` that is too small will likely produce a result that captures the idiosyncrasies within the data, while having a `k` that is too high will aggregate too many data points and produce inaccurate results as well.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Your task is to write a function that calculates the Euclidean distance of 2 points that are of type list and returns the distance. Below is the function prototype:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclidean_distance(x, y):\n",
    "    d = 0.0\n",
    "    \n",
    "    # write your calculations here\n",
    "\n",
    "    \n",
    "    return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "euclidean_distance([2,2],[4,4])\n",
    "# answer 2.8284271247461903"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## kNN and the problem of scale"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Datasets with features of different scale or magnitude can have a detrimental effect on the accuracy of kNN**. Features at different scales will affect the outcome of the distance metrics at a proportional degree to their magnitude. This means that if the feature scales in the dataset are not consistent with their importance, then they will have a disproportionate effect or bias on the final result which will lead to a degraded accuracy.\n",
    "\n",
    "For example, given a kNN problem of predicting house prices based on a house's number of bedrooms (ranging from 1 - 10) and a house's ratable value (anywhere from $100,000 - $10,000,000), which feature do you believe will dominate the equation for determining the Euclidean distance?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#house you're interested in\n",
    "x = [4, 400000]\n",
    "\n",
    "#house 1\n",
    "n1 = [1, 401000]\n",
    "\n",
    "#house 2\n",
    "n2 = [4, 402000]\n",
    "\n",
    "euclidean_distance(x, n1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "euclidean_distance(x, n2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## kNN and data normalization/standardization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Normalization (or Min-Max scaling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this approach, the data is scaled to a fixed range - usually 0 to 1.  \n",
    " \n",
    "The cost of having this bounded range is that we will end up with smaller standard deviations, which can suppress the effect of outliers.\n",
    "\n",
    "Normalization is typically done via the following equation:\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} X_{norm} = \\frac{x_i - X_{min}}{X_{max}-X_{min}} \\end{equation} $$\n",
    "</div>\n",
    "\n",
    "\n",
    "**Exercise:**: Given a list [10,20,30,40] write function code to produce a normalized list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize(x):\n",
    "    x_norm = []\n",
    "    \n",
    "    #your code\n",
    "\n",
    "    \n",
    "    return x_norm\n",
    "\n",
    "x = [10, 20, 30, 40]\n",
    "normalize(x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes we need to transform values into a specific range: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def scale(x, target_range):\n",
    "    x_scaled = []\n",
    "    \n",
    "    #your code\n",
    "\n",
    "    return x_scaled\n",
    "\n",
    "x = [0, 20, 30, 40]\n",
    "scale(x, [0,255])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Standardization (or Z-score normalization)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One alternative to normalization is **standardization**. The result of **standardization** (or **Z-score normalization**) is that the features will be rescaled so that they'll have the properties of a standard normal distribution with   \n",
    "\n",
    "\n",
    "\n",
    " $\\mu = 0$ and $\\sigma = 1$ \n",
    "\n",
    "\n",
    "\n",
    "where $\\mu$ is the mean (average) and $\\sigma$ is the standard deviation from the mean; standard scores (also called ***z*** scores) of the samples are calculated as follows:\n",
    "\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} z = \\frac{x - \\mu}{\\sigma}\\end{equation} $$\n",
    "</div>\n",
    "\n",
    " \n",
    "\n",
    "and standard deviation:  \n",
    "\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation}\\sigma = \\sqrt{\\frac{1}{N} \\sum_{i=1}^N (x_i - \\mu)^2}\\end{equation} $$\n",
    "</div>\n",
    "\n",
    "\n",
    "\n",
    "Standardizing the features so that they are centered around 0 with a standard deviation of 1 is not only important if we are comparing measurements that have different units, but it is also a general requirement for many machine learning algorithms. \n",
    "\n",
    "**Exercise:**: Given a list [10,20,30,40] write function code to produce a standardized list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def standardize(x):\n",
    "    x_stand = []\n",
    "    \n",
    "    #your code\n",
    "\n",
    "    \n",
    "    return x_stand\n",
    "\n",
    "x = [10, 20, 30, 40]\n",
    "standardize(x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, the problem with the standard score is that it is greatly influenced by outliers. The presence of outliers can have significant effects on the means, because of this, the standard Z-score formula is sometimes altered to:\n",
    "\n",
    "\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} \\frac{x_i - median}{aad} \\end{equation} $$\n",
    "</div>\n",
    "\n",
    "\n",
    "where the average absolute deviation ($aad$) is:\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} \\frac{1}{n}\\sum_{i=1}^n |x_i-median(X)| \\end{equation} $$\n",
    "</div>\n",
    "\n",
    "where $n$ is the number of samples.\n",
    "\n",
    "\n",
    "\n",
    "The above is called the **Modified Standard Score** and is more robust in noisy datasets where outliers are common.\n",
    "\n",
    "**Exercise:**: Given a list [10,20,30,40 write function code to produce a list that has been transformed into the Modified Standard Score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mod_standard_score(x):\n",
    "    x_mss = []\n",
    "    \n",
    "    #your code\n",
    "\n",
    "    return x_mss\n",
    "\n",
    "x = [10, 20, 30, 40]\n",
    "mod_standard_score(x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The effects of the above scaling techniques is depicted below using our student grades dataset.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grades = pd.read_csv(\"..\\datasets\\grades_prediction_mode.csv\", index_col=0)\n",
    "grades.head()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see in the table above, the features **A5** and **Exam**  are measured on different scales, so that ***Feature Scaling*** is necessary and important prior to any comparison or combination of these data.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import preprocessing\n",
    "\n",
    "std_scale = preprocessing.StandardScaler().fit(grades[['A5', 'Exam']].dropna())\n",
    "df_std = std_scale.transform(grades[['A5', 'Exam']].dropna())\n",
    "\n",
    "minmax_scale = preprocessing.MinMaxScaler().fit(grades[['A5', 'Exam']].dropna())\n",
    "df_minmax = minmax_scale.transform(grades[['A5', 'Exam']].dropna())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots()\n",
    "fig.set_size_inches(12,8)\n",
    "ax.scatter(grades['A5'], grades['Exam'], \n",
    "            color='green', label='input scale', alpha=0.5)\n",
    "\n",
    "ax.scatter(df_std[:,0], df_std[:,1], color='red', \n",
    "            label='Standardized [$N  (\\mu=0, \\; \\sigma=1)$]', alpha=0.3)\n",
    "\n",
    "ax.scatter(df_minmax[:,0], df_minmax[:,1], \n",
    "            color='blue', label='Normalized [min=0, max=1]', alpha=0.3)\n",
    "\n",
    "ax.set_title('A5 and Exam results displayed in raw, standardised and normalised forms')\n",
    "ax.set_xlabel('A5')\n",
    "ax.set_ylabel('Exam')\n",
    "#ax.legend()\n",
    "ax.grid()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.preprocessing import RobustScaler\n",
    "\n",
    "robustscaler_scale = preprocessing.RobustScaler(quantile_range=(25, 75)).fit(grades[['A5', 'Exam']].dropna())\n",
    "df_robustscaler = robustscaler_scale.transform(grades[['A5', 'Exam']].dropna())\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "fig.set_size_inches(12,8)\n",
    "ax.scatter(grades['A5'], grades['Exam'], \n",
    "            color='green', label='input scale', alpha=0.5)\n",
    "\n",
    "ax.scatter(df_std[:,0], df_std[:,1], color='red', \n",
    "            label='Standardized [$N  (\\mu=0, \\; \\sigma=1)$]', alpha=0.3)\n",
    "\n",
    "ax.scatter(df_minmax[:,0], df_minmax[:,1], \n",
    "            color='blue', label='Normalized [min=0, max=1]', alpha=0.3)\n",
    "\n",
    "ax.scatter(df_robustscaler[:,0], df_robustscaler[:,1], \n",
    "            color='blue', label='Robust Scaler [min=0, max=1]', alpha=0.3)\n",
    "\n",
    "\n",
    "ax.set_title('A5 and Exam results displayed in raw, standardised and normalised forms')\n",
    "ax.set_xlabel('A5')\n",
    "ax.set_ylabel('Exam')\n",
    "#ax.legend()\n",
    "ax.grid()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other normalisation techniques\n",
    "\n",
    "### Feature Clipping\n",
    "\n",
    "Often, some of your features may contain extreme outliers. A suitable strategy in this instance could be to clip the values for that feature by essentially setting up a threshold, so that values that are above (or below) are removed from the data. Feature clipping can be applied as a technique before before or after other normalizations are carried out.\n",
    "\n",
    "### Log Scaling\n",
    "\n",
    "Log scaling applies the logarithm to your feature values, which has the effect of compressing very long tailed distributions into a more narrow range of values. This technique is particularly useful when your feature has has many points clustered around a narrow range while the remainder is distributed very widely. This kind of a distribution is known as the power law distribution. Log scaling changes alters the distribution, helps improve model performance on  a number of algorithms but it also aids in visualisation and EDA.\n",
    "\n",
    "\n",
    "\n",
    "## Summary\n",
    "\n",
    "Normalisation is a pre-processing step in machine learning, and can also be a valuable part of EDA. The aim is to alter the values and align them to a common scale with the rest of the dataset, without significantly  distorting differences in the ranges of those values.\n",
    "\n",
    "Like most things in machine learning, it isn't always (or usually) obvious which normalisation technique will work best for your problem. Therefore, trial-and-error is an indispensable component at every stage of machine learning, and that includes normalisation. The best normalisation approach is essentially the one that empirically produces the best results. It is the only thing that matters in the end.\n",
    "\n",
    "In saying that, not all machine learning algorithms benefit from feature scaling. However, there are a couple of proven benefits of scaling features in respect to certain algorithms which go beyond just producing more stable models. It has been shown that feature scaling will often accelerate the convergence speed of stochastic gradient descent. Meanwhile, find support vectors for Support Vector Machines (SVM) has also been shown to take less time of combined with feature scaling. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternative similarity metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far we have learned how to apply the Euclidean distance metric as a measure of similarity between two points. Though this is a very simplistic measure, it is used surprisingly frequently in real world applications and is always the baseline metric against which to experiment with more complex measures. Therefore,  Euclidean distance is a good starting point and often there is no need to proceed to more complex solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Euclidean distance has **weaknesses** though. When we have data that is dense (all features more or less have meaningful values), then the Euclidean distance is ideal. In situations where the data is however is **sparse**, it **no longer becomes a useful measure**. \n",
    "\n",
    "This happens most often in text classification, information retrieval and recommender engines. Text classification usually relies on counting the frequency of occurrences of key words in order to classify if a document or article is for example from a sports, news, finance category etc. The problem is that languages are made up of tens of thousands of words, so many words that are common in for example, sports articles, will not occur in finance articles or documents. In this case we end up with sparse data and determining a meaningful distance measure in this instance becomes a challenge. Similar situation arises in recommender engines and user data that encodes preferences or ratings across hundreds of thousands possible products, where each customer has provided feedback on only a small portion of available products."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cosine similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To mitigate the above problem, the Cosine similarity metric was devised and works very well on this problem domain (as well as others like recommender engines or collaborative filtering). **Cosine similarity is not affected by missing values** in the comparison of the two vectors and is **also unaffected by the size (magnitude) of the vectors being compared**. Thus, when comparing documents or customer preferences,  it takes out the influence of the document length or the number of preferences in the calculation and **focuses only on the commonalities**.\n",
    "\n",
    "Cosine similarity calculates the cosine of the angle between two items. It is a measure of similarities between the orientations of two vectors. The cosine of 0 degrees (perfect similarity) is 1, and it is less than 1 for any other angle. Thus, two vectors with the same orientation have a cosine similarity of 1, two vectors at 90 degrees have a similarity of 0, and two vectors diametrically opposed have a similarity of -1. Its outcome is neatly bounded between -1 and 1. \n",
    "\n",
    "Below is the equation for it:\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} \\text{cosine similarity}  = {A \\cdot B \\over \\|A\\| \\|B\\|} = \\frac{ \\sum\\limits_{i=1}^{n}{A_i \\cdot B_i} }{ \\sqrt{\\sum\\limits_{i=1}^{n}{(A_i)^2}} \\times \\sqrt{\\sum\\limits_{i=1}^{n}{(B_i)^2}} } \\end{equation}\n",
    " $$\n",
    "</div>\n",
    "\n",
    "where $·$ indicates the dot product and $||x||$ indicates the length of the vector $x$. The dot product of two vectors x = [1,2,3] and y = [3,4,5] is:\n",
    "\n",
    "$x · y = (1 \\times 3) + (2 \\times 4) +(3 \\times 5)\n",
    "   = 3 + 8 + 15\n",
    "   = 26$\n",
    "   \n",
    "The length of vector $x$ is:\n",
    "\n",
    "$x_{len} = \\sqrt{1^2 + 2^2 + 3^2} = \\sqrt{1 + 4 + 9} = \\sqrt{14}$\n",
    "\n",
    "   \n",
    "**Exercise:**: Write a function which takes in two vectors (lists) and returns the Cosine similarity value. (hint: np.linalg.norm() produces the length of a vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math \n",
    "import numpy as np\n",
    "\n",
    "def cosine_similarity_distance(x, y):\n",
    "    d = 0.0\n",
    "    dot_prod = 0.0\n",
    "    x_len = 0.0\n",
    "    y_len = 0.0\n",
    "    \n",
    "    # write your calculations here\n",
    "\n",
    "    \n",
    "    d = dot_prod / (x_len * y_len)\n",
    "    \n",
    "    return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cosine_similarity_distance([3, 45, 7, 2], [3, 45, 7, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cosine_similarity_distance([3, 45, 7, 2], [-3, -45, -7, -2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cosine_similarity_distance([3, 45, 7, 2], [20, -1, -10, 50])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Jaccard similarity coefficient, referred to as the **'coefficient of community'**, was defined by Paul Jaccard. \n",
    "\n",
    "Unlike the Cosine similarity which considers only the similarity of two sets, Jaccard considers both the **similarity and diversity** of sample sets, while ignoring joint absences. \n",
    "\n",
    "Jaccard coefficient is widely used in recommender engines and collaborative filtering, as well as in ecology, biology and general scientific research.\n",
    "\n",
    "The Jaccard coefficient is **defined as the size (absolute value) of the intersection divided by the size of the union of the sample sets**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} \\text{Jaccard}(A,B) = {{|A \\cap B|}\\over{|A \\cup B|}} \\end{equation}\n",
    " $$\n",
    "</div>\n",
    "\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jaccard_similarity(x,y):\n",
    "    x = set(x)\n",
    "    y = set(y)\n",
    "    intersection = len(set.intersection(x,y))\n",
    "    union = len(set.union(x, y))\n",
    "    \n",
    "    return intersection / float(union)\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "johns_likes = ['Tennis','Cricket','Rugby','Swimming', 'Rowing']\n",
    "marys_likes = ['Tennis','Netball','Yoga','Swimming']\n",
    "peters_likes = ['Tennis','Cricket','Rugby','Soccer']\n",
    "\n",
    "jaccard_similarity(johns_likes, marys_likes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "jaccard_similarity(johns_likes, peters_likes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## kNN and weighted decision aggregation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say we are using kNN as the algorithm to to perform a regression, where $k > 1$ and in our example we will make $k = 3$. Ordinarily, we would find the 3 closest neighbours, extract the target values from the neighbours that we are trying to predict for some sample $x$. We would then aggregate this target value by finding the mean, and assign the mean as our predicted value for $x$.\n",
    "\n",
    "Is this the best way to aggregate though? What if amongst the three neighbours, one is very close to the point $x$, while the other two are significantly further away? Should the two neghbours that are much further away than the first neighbour have an equal input into the final aggregate value?\n",
    "\n",
    "Particularly in instances where there is some degree of sparsity in the dataset, it makes sense to employ **weighted calculations**, making use of aggregation, whereby **proportional importance** is assigned to different points according to some metric. \n",
    "\n",
    "Here we will consider the distance of each neighbour as the degree to which they will influence the final decision.\n",
    "\n",
    "Say we have our point x and 3 closest neighbours to x:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1,2,3] # y=?\n",
    "n1 = [3,4,5] # y=80\n",
    "n2 = [5,4,5] # y=70\n",
    "n3 = [10,14,1] # y=55\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.mean([80, 70, 55])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#distances\n",
    "euclidean_distance(x, n1) # = 3.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "euclidean_distance(x, n2) # = 4.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "euclidean_distance(x, n3) # = 15.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum_of_distances = euclidean_distance(x, n1) + euclidean_distance(x, n2) + euclidean_distance(x, n3)\n",
    "sum_of_distances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now add up the sum of all distances to point $x$, and create a vector $W$ of proportional influences where the distance of each neighbour $n$ is divided by the sum, and the result subtracted from 1.\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} \\text{sum of distances} = SD = \\sum_{i=1}^k eucledean\\_distance(n_i) \\end{equation} $$\n",
    "</div>\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\begin{equation} \\text{vector of weights}  = W = 1- \\frac{eucledean\\_distance(n_i)}{SD} \\end{equation} $$\n",
    "</div>\n",
    "\n",
    "\n",
    "**Exercise:**: Write a function which takes in a vector $x$ and a list of $k$ vector representing the closest neighbours, and returns a vector of calculated weights for each neighbour:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_neghbour_weights(x, neighbours, k):\n",
    "    weights = []\n",
    "    sd = 0.0\n",
    "    \n",
    "    #your code here\n",
    "    #call your distance metric function of choice here - pick from one you defined above\n",
    "\n",
    "    \n",
    "    return weights\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1,2,3]\n",
    "k = 3\n",
    "n1 = [3,4,5]\n",
    "n2 = [5,4,5]\n",
    "n3 = [10,14,1]\n",
    "\n",
    "neighbours = [n1, n2, n3]\n",
    "\n",
    "print(np.sum(calculate_neghbour_weights(x, neighbours, k)))\n",
    "calculate_neghbour_weights(x, neighbours, k)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Weighted average calculation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Formally, the weighted mean of a non-empty vector\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\{x_1, x_2, \\dots , x_n\\}, $$\n",
    "</div>\n",
    "    \n",
    "\n",
    "with non-negative weights, is calculated as the sum of the product of weights and associated values, divided by the sum of weights \n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$ \\bar{x} = \\frac{ \\sum_{i=1}^n w_i x_i}{\\sum_{i=1}^n w_i}, $$\n",
    "</div>\n",
    "    \n",
    "expanded:\n",
    "\n",
    "<div style=\"font-size: 140%;\">  \n",
    "$$  \\bar{x} = \\frac{w_1 x_1 + w_2 x_2 + \\cdots + w_n x_n}{w_1 + w_2 + \\cdots + w_n}. $$\n",
    "</div>\n",
    "    \n",
    "\n",
    "Therefore data elements with a high weight contribute more to the weighted mean than do elements with a low weight."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = [80,70,55]\n",
    "\n",
    "np.dot(calculate_neghbour_weights(x, neighbours, k), y) / np.sum(calculate_neghbour_weights(x, neighbours, k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction to Python's Machine Learning Toolkit Scikit-Learn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "scikit-learn is Python's flagship library for machine learning and data mining with many implemented and ready to use  algorithms.\n",
    "\n",
    "Fast and efficient versions of kNN are implemented in this library. There are two versions of kNN in scikit-learn. One is designed for regression problems (**KNeighborsRegressor**) and the other for classification problems (**KNeighborsClassifier**). \n",
    "\n",
    "There are several key tunable parameters which can be passed to the learning algorithm. We can specify:\n",
    "\n",
    "1. weighted or uniform distances --> weights = ['distance', 'uniform']\n",
    "2. size of k  --> n_neighbors = 5\n",
    "3. the choice of search algorithm to control efficiency - set through the keyword 'algorithm', which must be one of ['auto', 'ball_tree', 'kd_tree', 'brute']\n",
    "4. resemblance/distance measure - set through the keyword metric, with the following options below:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "**Metrics intended for real-valued vector spaces:**\n",
    "\n",
    "==============  ====================  ========  ===============================\n",
    "identifier      class name            args      distance function\n",
    "--------------  --------------------  --------  -------------------------------\n",
    "\"euclidean\"     EuclideanDistance     -         ``sqrt(sum((x - y)^2))``\n",
    "\"manhattan\"     ManhattanDistance     -         ``sum(|x - y|)``\n",
    "\"chebyshev\"     ChebyshevDistance     -         ``sum(max(|x - y|))``\n",
    "\"minkowski\"     MinkowskiDistance     p         ``sum(|x - y|^p)^(1/p)``\n",
    "\"wminkowski\"    WMinkowskiDistance    p, w      ``sum(w * |x - y|^p)^(1/p)``\n",
    "\"seuclidean\"    SEuclideanDistance    V         ``sqrt(sum((x - y)^2 / V))``\n",
    "\"mahalanobis\"   MahalanobisDistance   V or VI   ``sqrt((x - y)' V^-1 (x - y))``\n",
    "==============  ====================  ========  ===============================\n",
    "\n",
    "**Metrics intended for two-dimensional vector spaces:**\n",
    "\n",
    "============  ==================  ========================================\n",
    "identifier    class name          distance function\n",
    "------------  ------------------  ----------------------------------------\n",
    "\"haversine\"   HaversineDistance   2 arcsin(sqrt(sin^2(0.5*dx)\n",
    "                                         + cos(x1)cos(x2)sin^2(0.5*dy)))\n",
    "============  ==================  ========================================\n",
    "\n",
    "\n",
    "**Metrics intended for integer-valued vector spaces:**  Though intended\n",
    "for integer-valued vectors, these are also valid metrics in the case of\n",
    "real-valued vectors.\n",
    "\n",
    "=============  ====================  ========================================\n",
    "identifier     class name            distance function\n",
    "-------------  --------------------  ----------------------------------------\n",
    "\"hamming\"      HammingDistance       ``N_unequal(x, y) / N_tot``\n",
    "\"canberra\"     CanberraDistance      ``sum(|x - y| / (|x| + |y|))``\n",
    "\"braycurtis\"   BrayCurtisDistance    ``sum(|x - y|) / (sum(|x|) + sum(|y|))``\n",
    "=============  ====================  ========================================\n",
    "\n",
    "**Metrics intended for boolean-valued vector spaces:**  Any nonzero entry\n",
    "is evaluated to \"True\".  In the listings below, the following\n",
    "abbreviations are used:\n",
    "\n",
    " - N  : number of dimensions\n",
    " - NTT : number of dims in which both values are True\n",
    " - NTF : number of dims in which the first value is True, second is False\n",
    " - NFT : number of dims in which the first value is False, second is True\n",
    " - NFF : number of dims in which both values are False\n",
    " - NNEQ : number of non-equal dimensions, NNEQ = NTF + NFT\n",
    " - NNZ : number of nonzero dimensions, NNZ = NTF + NFT + NTT\n",
    "\n",
    "=================  =======================  ===============================\n",
    "identifier         class name               distance function\n",
    "-----------------  -----------------------  -------------------------------\n",
    "\"jaccard\"          JaccardDistance          NNEQ / NNZ\n",
    "\"maching\"          MatchingDistance         NNEQ / N\n",
    "\"dice\"             DiceDistance             NNEQ / (NTT + NNZ)\n",
    "\"kulsinski\"        KulsinskiDistance        (NNEQ + N - NTT) / (NNEQ + N)\n",
    "\"rogerstanimoto\"   RogersTanimotoDistance   2 * NNEQ / (N + NNEQ)\n",
    "\"russellrao\"       RussellRaoDistance       NNZ / N\n",
    "\"sokalmichener\"    SokalMichenerDistance    2 * NNEQ / (N + NNEQ)\n",
    "\"sokalsneath\"      SokalSneathDistance      NNEQ / (NNEQ + 0.5 * NTT)\n",
    "=================  =======================  ===============================\n",
    "\n",
    "**User-defined distance:**\n",
    "\n",
    "===========    ===============    =======\n",
    "identifier     class name         args\n",
    "-----------    ---------------    -------\n",
    "\"pyfunc\"       PyFuncDistance     func\n",
    "===========    ===============    =======\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nearest Neighbor Search Algorithms (from http://scikit-learn.org)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the **drawbacks of kNN is the computational overhead** in calculating distances during the classification/runtime. Research into more efficient methods is still an ongoing area of study. \n",
    "\n",
    "The most naive search algorithms  involves the brute-force computation of distances between all pairs of points in the dataset. Given N samples in D dimensions, this approach has a quadratic computational complexity of:\n",
    "\n",
    "<div style=\"font-size: 150%;\">  \n",
    "$$ \\text{Brute force} = O(D N^2) $$\n",
    "</div>\n",
    "\n",
    "Efficient brute-force algorithms can be very competitive for small data samples. However, **as the number of samples N grows, the brute-force approach quickly becomes infeasible**.\n",
    "\n",
    "To address the computational inefficiencies of the brute-force approach, a variety of **tree-based data structures** have been invented. In general, these structures attempt to reduce the required number of distance calculations by efficiently encoding aggregate distance information for the sample. The basic idea is that if point A is very distant from point B, and point B is very close to point C, then we know that points A and C are very distant, without having to explicitly calculate their distance. An early approach to taking advantage of this aggregate information was the KD tree data structure. \n",
    "\n",
    "Though the **KD tree approach is very fast for low-dimensional (D < 20) neighbors searches**, it becomes inefficient as D grows very large: this is one manifestation of the so-called “curse of dimensionality”.\n",
    "\n",
    "KD tree query time changes with D in a way that is difficult to precisely characterise. For small D (less than 20 or so) the cost is approximately loglinear O[D log(N)], and the KD tree query can be very efficient. For larger D, the cost increases to nearly that of the brute force approach.\n",
    "\n",
    "<div style=\"font-size: 150%;\">  \n",
    "$$ \\text{KDTree} = O(D \\log(N)) $$\n",
    "</div>\n",
    "\n",
    "\n",
    "To address the inefficiencies of KD Trees in higher dimensions, the ball tree data structure was developed. Where KD trees partition data along Cartesian axes, ball trees partition data in a series of nesting hyper-spheres. This makes tree construction more costly than that of the KD tree, but results in a data structure which can be very efficient on highly-structured data, even in very high dimensions.  The **ball tree can out-perform a KD-tree in high dimensions**, though the actual performance is highly dependent on the structure of the training data.\n",
    "\n",
    "<div style=\"font-size: 150%;\">  \n",
    "$$ \\text{BallTree} = O(D \\log(N)) $$\n",
    "</div>\n",
    "\n",
    "Alternatively, if the 'algorithm' parameter is not specified, kNN will automatically discern which search algorithm to employ by passing in the default 'auto' value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example (Regression)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will first have a look at regression using kNN and how the model is affected when using uniform versus weighted neighbour aggregation.\n",
    "\n",
    "The problem below looks at the familiar student grade prediction. We will try to model student total grades based on exam results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import neighbors\n",
    "import seaborn as sns\n",
    "from pylab import rcParams\n",
    "rcParams['figure.figsize'] = 14, 8\n",
    "rcParams['font.size'] = 20\n",
    "rcParams['figure.dpi'] = 350\n",
    "rcParams['lines.linewidth'] = 2\n",
    "rcParams['axes.facecolor'] = 'white'\n",
    "rcParams['patch.edgecolor'] = 'white'\n",
    "rcParams['font.family'] = 'StixGeneral'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grades = pd.read_csv('..\\datasets\\grades_prediction_mode.csv')\n",
    "grades = grades.dropna()\n",
    "grades.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = grades.Exam.values\n",
    "X = np.reshape(X, (len(grades.Exam), 1))\n",
    "y = grades.Total.values\n",
    "y = np.reshape(y, (len(grades.Total), 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fit regression model\n",
    "x = np.linspace(0, 60, 400)[:, np.newaxis]\n",
    "n_neighbors = 5\n",
    "\n",
    "for i, weights in enumerate(['uniform', 'distance']):\n",
    "    knn = neighbors.KNeighborsRegressor(n_neighbors, weights=weights)\n",
    "    y_hat = knn.fit(X, y).predict(x)\n",
    "    \n",
    "    plt.subplot(2, 1, i + 1)\n",
    "    plt.scatter(X, y, c='k', label='data')\n",
    "    plt.plot(x, y_hat, c='b', label='prediction')\n",
    "    plt.axis('tight')\n",
    "    plt.xlabel('Exam')\n",
    "    #plt.ylabel('Total')\n",
    "    plt.legend(loc='upper left')\n",
    "    plt.title(\"KNeighborsRegressor (k = %i, weights = '%s')\" % (n_neighbors, weights))\n",
    "    plt.subplots_adjust( hspace=0.5)\n",
    "    \n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** Experiment on the above problem with different values of k. Which is the most optimal for this dataset? Why? How could you empirically confirm this?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above example, varying the distance metric will not make any difference since we are only using one dimension. However, varying the value of k will make a big difference to the model. We will now see how we can empirically determine what is the best value of k for this dataset.\n",
    "\n",
    "For this, we will use the RMSE and the R^2 metrics.\n",
    "\n",
    "First of all, let's train the model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn = neighbors.KNeighborsRegressor(n_neighbors=5, weights='uniform')\n",
    "mod = knn.fit(X, y)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we will create and array of exam values with a very small amount of jitter (otherwise the nans are returned)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "x = np.reshape(grades.Exam.values, (len(grades.Exam), 1)) + 0.0001\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we create the predicted values: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "y_hat = mod.predict(x)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, define a method that calculates the R^2 and the RMSE measures:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_regression_goodness_of_fit(ys, y_hat):\n",
    "    ss_total = 0\n",
    "    ss_residual = 0\n",
    "    ss_regression = 0\n",
    "    y_mean = y.mean()\n",
    "    \n",
    "    for i in range(len(ys)):\n",
    "        ss_total += np.square(ys[i] - y_mean)\n",
    "        ss_residual += np.square(ys[i] - y_hat[i])\n",
    "        ss_regression += np.square(y_hat[i] - y_mean)\n",
    "    \n",
    "    r_square = ss_regression / ss_total\n",
    "    rmse = np.sqrt( ss_residual / float(len(ys)) )\n",
    "    \n",
    "    return r_square[0], rmse[0]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_regression_goodness_of_fit(y, y_hat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we know that the function works, we want to re-train the model with different values of k, beginning with 2 to the size of the dataset, and inspect the effect that varying k has on the accuracy measures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rsquare_arr = []\n",
    "rmse_arr = []\n",
    "\n",
    "for k in range(2, len(y)):\n",
    "    knn = neighbors.KNeighborsRegressor(n_neighbors=k)\n",
    "    y_hat = knn.fit(X, y).predict(x)\n",
    "    rsquare, rmse = calculate_regression_goodness_of_fit(y, y_hat)\n",
    "    rmse_arr.append(rmse)\n",
    "    rsquare_arr.append(rsquare)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.subplot(2, 1, 1)\n",
    "plt.plot(range(2, 91), rsquare_arr, c='k', label='R Square')\n",
    "plt.axis('tight')\n",
    "plt.xlabel('k number of nearest neighbours')\n",
    "plt.ylabel('RSquare')\n",
    "plt.legend(loc='upper right')\n",
    "plt.title(\"RSquare for the KNeighborsRegressor\")\n",
    "plt.subplots_adjust( hspace=0.5)\n",
    "\n",
    "plt.subplot(2, 1, 2)\n",
    "plt.plot(range(2, 91), rmse_arr, c='k', label='RMSE')\n",
    "plt.axis('tight')\n",
    "plt.xlabel('k number of nearest neighbours')\n",
    "plt.ylabel('RMSE')\n",
    "plt.legend(loc='upper left')\n",
    "plt.title(\"RMSE for the KNeighborsRegressor\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** Discuss the meaning of the above graphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise** Generate the above graphs for the regression task of predicting the student exam outcome based on the course work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example (Classification)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of predicting a continuous valued output, classification on the other hand predicts a class label or a category. The mechanics are however very much the same for both versions of kNN. \n",
    "\n",
    "In this example, we will look at the student grades problem again and will attempt to predict a student's final grade (categorical), based on assignment 1,2 and 3 marks. \n",
    "\n",
    "**Recall that normalization is a crucial step in kNN when dealing with multivariate data. The code below has not normalized the features and this is left as an exercise for you to complete at home, and to explore how this affects the final outcomes.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grades.dtypes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create numeric column for the response\n",
    "# note: features and response must both be entirely numeric!\n",
    "mapping = {'A+':0, 'A':1, 'A-':2 ,'B+':3, 'B':4, 'B-':5, 'C+':6, 'C':7, 'R':8, 'D':9,'E':10}\n",
    "grades['grade_num'] = grades.Grade.map(mapping)\n",
    "\n",
    "# create X (features) three different ways\n",
    "X = grades[['A3', 'A4', 'A5']]\n",
    "#X = grades.loc[:, 'A3':'A5']\n",
    "#X = grades.iloc[:, 0:3]\n",
    "\n",
    "# create y (response)\n",
    "y = grades.grade_num\n",
    "\n",
    "# check the shape of X and y\n",
    "print(X.shape)     # 91 by 3 (n=91, p=3)\n",
    "print(y.shape)     # 91 (must match first dimension of X)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# scikit-learn 4-step modeling pattern:\n",
    "\n",
    "# Step 1: import the class you plan to use\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "# Step 2: instantiate the model\n",
    "# note: all unspecified parameters are set to the defaults\n",
    "knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 3: fit the model with data (learn the relationship between X and y)\n",
    "knn.fit(X, y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step 4: use the \"fitted model\" to predict the response for a new observation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = dict(zip(['A3', 'A4', 'A5'], [4, 5, 6]))\n",
    "d         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "df = pd.DataFrame.from_dict(d, orient='index').T\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# make a perdiction\n",
    "res = knn.predict(df)\n",
    "[key for key in mapping if mapping[key] == res ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# predict for multiple observations at once\n",
    "X_new = pd.DataFrame(columns=['A3', 'A4', 'A5'])\n",
    "X_new.loc[0] = [3, 5, 4]\n",
    "X_new.loc[1] = [6, 10, 12]\n",
    "\n",
    "res = knn.predict(X_new)\n",
    "\n",
    "[key for key in mapping if mapping[key] == res[0] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[key for key in mapping if mapping[key] == res[1] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# try a different value of K (\"tuning parameter\")\n",
    "knn = KNeighborsClassifier(n_neighbors=3)\n",
    "knn.fit(X, y)\n",
    "res = knn.predict(X_new)\n",
    "\n",
    "print([key for key in mapping if mapping[key] == res[0] ])\n",
    "print(\"predicted probabilities of class membership: \" + str(knn.predict_proba(X_new)[0]))        # predicted probabilities of class membership\n",
    "\n",
    "print([key for key in mapping if mapping[key] == res[1] ])\n",
    "print(\"predicted probabilities of class membership: \" + str(knn.predict_proba(X_new)[1]) )       # predicted probabilities of class membership\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:**: Modify the above to make predictions based solely on the exam result. Compare the predictions when using A1,A2 and A3 and Exam as predictor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## When to Use k-Nearest Neighbours"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nearest neighbours algorithm has been successful in a broad range of classification and regression problems. These include handwritten digits and satellite image scenes. Due to the fact that it is a non-parametric method, it is often effective in classification situations where the decision boundary is very irregular. \n",
    "\n",
    "Some other advantages it has over other methods include the ability to add new observations to the data without any computational effort and the easy of understanding and interpreting the outputs.\n",
    "\n",
    "\n",
    "The few disadvantages of the nearest neighbours algorithm include its computational intensity when making predictions because the distance to every point has to be calculated; however, there are ways that this can to a degree be mitigated. Nearest neighbours algorithm is also sensitive to noisy and irrelevant features."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
